package com.liunian.algorithmstudy.backtracking.range;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Permute46 {

	/**
	 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

	 示例 1：
	 输入：nums = [1,2,3]
	 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

	 示例 2：
	 输入：nums = [0,1]
	 输出：[[0,1],[1,0]]

	 示例 3：
	 输入：nums = [1]
	 输出：[[1]]
	 */
	List<List<Integer>> res = new ArrayList<>();
	LinkedList<Integer> path = new LinkedList<>();
	public List<List<Integer>> permute(int[] nums) {
		backTracking(nums);
		return res;
	}

	private void backTracking(int[] nums) {
		if (path.size() == nums.length) {
			res.add(new ArrayList<>(path));
			return;
		}
		for (int i = 0; i < nums.length; i++) {
			if (!path.isEmpty() && path.contains(nums[i])) {
				continue;
			}
			path.add(nums[i]);
			backTracking(nums);
			path.removeLast();
		}
	}

	public static void main(String[] args) {
		Permute46 permute46 = new Permute46();
		System.out.println(permute46.permute(new int[]{1,2,3}));
	}

}
